package object;

import java.util.Arrays;

public class Test {
    public static void shiftDown(int[] arr,int size,int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < size) {
            if (child + 1 < size && arr[child + 1] < arr[child]) {
                child = child + 1;
            }
            if (arr[child] < arr[parent]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                //调整完毕，退出了
                break;
            }

        }

    }
    public static void shiftUp(int[] arr,int index) {
        if (index >= arr.length) {
            return;
        }
        int child = index;
        int parent = (child - 1) / 2;
        while (child > 0) {
           if (arr[child] < arr[parent]) {
               int tmp = arr[child];
               arr[child] = arr[parent];
               arr[parent] = tmp;
               child = parent;
               parent = (child - 1) / 2;
           } else {
               break;
           }

        }
    }
    public static void creadHeap(int[] arr) {
        int lastParent = arr.length - 1;
        int lastleaf = (lastParent - 1) / 2;
        for(int i = lastleaf;i >= 0;i--) {
            shiftDown(arr,arr.length,i);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,4,10,5,8,1,16};
        creadHeap(arr);
        System.out.println(Arrays.toString(arr));
    }

}
